package com.company.ljh.medium;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @description:
 * 394. 字符串解码
 * 中等
 * 1.5K
 * 相关企业
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/4 10:32
 * @version:1.0
 */
public class 字符串解码 {
    public static void main(String[] args) {
        decodeString("3[a]10[bc]");
    }
    //解法：使用栈来解析字符串，遇到]出栈组装字符串一直到[结尾，然后出栈找到数字，在将组装好的字符串入栈
    //注意：出栈后字符串和数字都反向，使用时需要倒转
    public  static  String decodeString(String s) {
        //以[为字符串开头，]为字符串结尾
        //[为出栈结束标记,]为开始出栈标记
        Stack<Character> stack = new Stack();
        int i=0;
        while( i <s.length()){
            if(s.charAt(i) == ']'){
                StringBuilder str = new StringBuilder();
                while(!stack.isEmpty()&&stack.peek()!='['){
                    //组装的字符串是反向的
                    str.append(stack.pop());
                }
                //移除"["
                stack.pop();
                StringBuilder numberStr = new StringBuilder();
                while(!stack.isEmpty()&&stack.peek() <='9' && stack.peek() >='0'){
                    numberStr.append(stack.pop());
                }
                //数字反向，因此需要倒转顺序
                int number = Integer.parseInt(numberStr.reverse().toString());
                for(int j=0;j<number;j++){
                    //反向入栈 调整为正向
                    for(int n=str.length()-1;n>=0;n--){
                        stack.push(str.charAt(n));
                    }
                }
            }else{
                stack.push(s.charAt(i));
            }
            i++;
        }
        char []result = new char[stack.size()];
        for(int j=result.length -1;j>=0;j--){
            result[j] = stack.pop();
        }
        return String.valueOf(result);
    }
}
